The present invention relates to a fast complex number multiplier which consumes little energy.
In current communication systems, the information is generally processed digitally. Digitization improves the quality and the performance of the transmission systems. Moreover, the increase in the bit rate of data transmitted and the development of ever more powerful software constrain the transmission systems to process a large amount of data in a record time, hence the importance of extremely high-performance calculation modules. One of these modules is the complex number multiplier found in practically any signal processing device such as mobile telephones, for example.
A multiplication of two complex numbers generally involves four real multiplication operations and two real addition and subtraction operations. Specifically, the multiplication of two complex numbers (A+jB) and (C+jD) can be broken down as follows:
(A+jB)(C+jD)=(ACxe2x88x92BD)+j(AD+BC)=R+jI 
With R=ACxe2x88x92BD, the real part of the product and I=AD+BC, the imaginary part of the product.
This breakdown clearly involves four real multiplications (AC; BD; AD and BC) and two real additions and multiplications (ACxe2x88x92BD and AD+BC).
A, B, C and D are binary numbers represented according to a two""s complement convention.
For a positive number, the first bit, called the xe2x80x9csign bitxe2x80x9d, is equal to zero, and the following bits code the absolute value of the relevant decimal number in natural binary.
For a negative number, the sign bit is equal to one, and the following bits code the absolute value of the relevant decimal number in two""s complement binary.
The real multiplication operations (AC, AD, BD, and BC) are particularly complex to implement.
In the prior art, use is made of a factoring technique for reducing the number of multiplication operations in return for addition and subtraction operations. This factorization, called xe2x80x9ctransformation by reduction of forcexe2x80x9d ultimately yields three multiplication operations and five addition and subtraction operations. A difficult multiplication operation has been swapped for three new addition and subtraction operations.
R=ACxe2x88x92BD=(Axe2x88x92B)C+(Cxe2x88x92D)B 
I=AD+BC=(A+B)D+(Cxe2x88x92D)B 
The five addition and subtraction operations are Axe2x88x92B, A+B, Cxe2x88x92D, (Axe2x88x92B)C+(Cxe2x88x92D)B, (A+B)D+(Cxe2x88x92D)B
The three multiplication operations are (Axe2x88x92B)C, (A+B)D, (Cxe2x88x92D)B
The terms (Axe2x88x92B), (A+B) and (Cxe2x88x92D) are called xe2x80x9cpremultiplication operationsxe2x80x9d since they are intended to feed real multipliers included in a complex number multiplier.
This method is of real benefit as regards energy consumption, since one less real multiplier is synonymous with a saving of space on the electronic circuit, hence with a decrease in energy consumption, the area used by a real multiplier generally being three times greater than that of a real adder.
However, the calculation execution time for a complex number multiplier using the transformation by reduction of force, is greater than a direct complex number multiplier performing the four multiplication operations and the two addition and subtraction operations. The complex number multiplier is consequently slower.
This speed limitation is due essentially to the propagation of the carry of the least significant bit (LSB) to the most significant bit (MSB) in the course of addition and subtraction operations.
Complex number multiplier devices are known which use the transformation by reduction of force while improving the speed of execution of calculation as compared with the direct method. Such a device has been described by B. W. Y. Wei, H. Du and H. Chen in xe2x80x9cA Complex-Number Multiplier Using Radix-4 Digitsxe2x80x9d, pages 84-90, 12th xe2x80x9cSymposium of Computer Arithmeticxe2x80x9d, Bath, England, 19 to 21 Jul. 1995.
In this method, the numbers are put into a redundant binary format, having numerous advantages. For example, the bit of a base two redundant binary number can take three values: xe2x88x921, 0 or 1, and enables the decimal number of value 5 to be represented, in redundant binary format, by:
[0101], [011{overscore (1)}], [1{overscore (1)}1], [1{overscore (1)}01] or [10{overscore (1)}{overscore (1)}]
A decimal number can thus be represented by five redundant binary numbers. This redundancy makes it possible to reduce the rules for adding two binary numbers by confining oneself, for each bit of the result, to considering only the two bits of like rank of the two operands. Thus, the additions and subtractions are performed without carry propagation. The execution time for such an addition or subtraction operation remains constant irrespective of the length of the operands. Moreover, this representation requires no specific device for taking account of the sign bit.
In the method proposed by Wei et al, the two""s complement binary numbers A, B, C and D are delivered to the input of a first stage composed of two subtractors and an adder, then the latter generates at the output the results (Axe2x88x92B), (A+B) and (Cxe2x88x92D) in a redundant binary format.
These results, also called xe2x80x9cpartial productsxe2x80x9d, are represented by a specific base two coding. The modules forming the first stage and performing the three addition and subtraction operations comprise inverters only.
These results then undergo a conversion from the base two to a base four in a second stage so as to reduce the length of the binary numbers forming these results and to feed three real number multipliers in a third stage.
The final result is supplied by two real adders which, from the results of the three real multipliers, generate a real part and an imaginary part. However, this device comprises very many components, this being penalizing in terms of energy dissipation.
The invention aims to afford a solution to this problem by reducing the number of logic gates required on the complex number multiplier so as to decrease consumption.
An aim of the invention is to reduce the execution time for multiplying two complex numbers.
In a general manner, the complex number multiplier comprises an input which is followed by four processing stages. The input makes it possible to receive the real part A and the imaginary part B of a first complex number, and the real part C and the imaginary part D of a second complex number, the numbers A, B, C, D being two""s complement coded binary numbers.
The first processing stage comprises subtraction means able to perform the operations Axe2x88x92B and Cxe2x88x92D, the result of each subtraction being a base two binary number with a redundant binary format and a borrow-save coding, and an adder module able to perform the operation A+B, the result of this addition being a base two binary number with a redundant format and a carry-save coding.
The second processing stage comprises conversion means able to convert the numbers delivered by the first processing stage into base four coded binary numbers with a redundant format.
The third processing stage comprises multiplication means able to perform the operations (Axe2x88x92B)C, (Cxe2x88x92D)B and (A+B)D, the result of these operations being base two coded numbers with a redundant format.
Finally, the fourth processing stage comprises two adders for computing the real part and the imaginary part of the product of the two input complex numbers from the numbers delivered by the third processing stage, these real and imaginary parts being to the base two according to a redundant binary format.
This implementation is achieved in accordance with the transformation by reduction of force. The latter therefore involves three multiplication operations and five addition operations. All the results from the four stages of the complex multiplier are in redundant binary format. This format makes it possible to perform the addition and subtraction operations with a carry propagation limited to one bit. Therefore, the saving in processing time obtained by using the multiplier according to the invention is noteworthy as compared, for example, with a multiplier performing the transformation by reduction of force with a two""s complement binary format.
According to one mode of implementation of the invention, the subtraction means comprise two distinct modules able to perform the operations Axe2x88x92B and Cxe2x88x92D. Advantageously, the subtractor module and adder module are embodied solely by wiring.
At its input, each subtraction module admits two two""s complement binary numbers, then performs a transformation so as to obtain a result in redundant binary format, that is to say, two bits coding a decimal number. The type of coding used to match the two bits to the decimal number is borrow-save coding, this making it possible to perform the subtraction operations with straightforward wiring without any logic gate. The cost of producing these two blocks is practically zero. The addition operation (A+B) also results in straightforward wiring since the result is in redundant binary format with carry-save coding, this being known to the person skilled in the art. Thus, the whole of the first stage is characterized by an almost zero cost.
In a preferred embodiment, the multiplication means comprise three distinct real multipliers able to perform the operations (Axe2x88x92B)C, (Cxe2x88x92D)B and (A+B)D respectively. Each multiplier advantageously comprises internal means able to perform the addition of two partial products X and Y by performing the operation Xxe2x88x92{overscore (Y)}xe2x88x921, where {overscore (Y)} denotes the 1""s complement of Y.
Specifically, the internal addition of two numbers (X+Y) is performed using the following transformation:
X+Y=Xxe2x88x92(xe2x88x92Y)=Xxe2x88x92({overscore (Y)}+1)=(Xxe2x88x92{overscore (Y)})xe2x88x921 
The internal means of the real multipliers preferably comprise an inverter for delivering the number {overscore (Y)} and a means of wiring for performing the subtraction Xxe2x88x92{overscore (Y)}.
According to an advantageous mode of implementation of the invention, the real multipliers and adders incorporate a borrow-save coding binary tree.
By using a fourth stage for conversion from base two to base four, it was made possible to halve the number of partial products to be added in the multipliers as compared with a conventional multiplier operating with the aid of two""s complement coded binary numbers. Furthermore, the use of borrow-save coding in the multipliers according to the invention also makes it possible to halve the number of partial products to be added at the level of the internal adders, i.e. a fourfold reduction as compared with a conventional multiplier.
The type of multiplier thus described comprises a regular cellular structure and dissipates less power than a conventional multiplier.
In a variant of the complex multiplier according to the invention, the real multipliers and adders incorporate a slightly modified borrow-save coding binary tree. The modification stems from the fact that any bit pair xe2x80x9c11xe2x80x9d, is transformed into a bit pair xe2x80x9c00xe2x80x9d, at the input of the real multipliers and adders. This makes it possible to perform fast internal additions with frugal consumption.